#pragma once

#include<iostream>
using namespace std;

namespace Wang
{
template<class T>
struct list_node
{
	T _val;
	list_node* _next;
	list_node* _prev;
	list_node(const T& x = T())
		:_val(x)
		,_next(this)
		,_prev(this)
	{ }
};

template<class T, class Ref, class Ptr>
struct list_iterator
{
	typedef list_node<T> node;
	typedef list_iterator<T, Ref, Ptr> Self;

    typedef ptrdiff_t				difference_type;
    typedef std::bidirectional_iterator_tag	iterator_category;
    typedef T				value_type;
    typedef Ptr		pointer;
    typedef Ref			reference;
	node* _ptr;
	list_iterator(node* ptr)
		:_ptr(ptr)
	{}

	Self& operator++()
	{
		_ptr = _ptr->_next;
		return *this;
	}

	Self& operator--()
	{
		_ptr = _ptr->_prev;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		_ptr = _ptr->_next;
		return tmp;
	}

	Self operator--(int)
	{
		Self tmp(*this);
		_ptr = _ptr->_prev;
		return tmp;
	}

	bool operator!= (const Self& it) { return _ptr != it._ptr; }
	bool operator== (const Self& it) { return _ptr == it._ptr; }
	Ref operator*() { return _ptr->_val; }
	Ptr operator->() { return &_ptr->_val; }
};

template<class T>
class list
{
	using node = list_node<T>;
	node* _head = new node;
public:
	list() {}

	list(const initializer_list<T>& il)
	{
		for (auto& e : il)
			push_back(e);
	}
	list(const list<T>& ls)
	{
		for (node* i = ls._head->_next; i != ls._head; i = i->_next)
			push_back(i->_val);
	}
	list<T>& operator= (const list<T>& ls)
	{
		if(this != &ls)
		{
			list<T> tmp(ls);
			swap(tmp);
		}
		return *this;
	}
	~list()
	{
		node* i = _head->_next;
		while (i != _head)
		{
			node* ne = i->_next;
			delete i;
			i = ne;
		}
		delete _head;
		_head = nullptr;
	}

	typedef list_iterator<T, T&, T*> iterator;
	//typedef const list_iterator<T> const_iterator; // err
	typedef list_iterator<T, const T&, const T*> const_iterator;

	iterator begin() { return _head->_next; }
	iterator end() { return _head; }

	const_iterator begin() const { return _head->_next; }
	const_iterator end() const { return _head; }

	void push_back(const T& x) { insert(--end(), x); }
	void pop_back() { erase(--end()); }
	void push_front(const T& x) { insert(--begin(), x); }
	void pop_front() { erase(begin()); }
	T& front() { return *begin(); }
	T& back() { return *(--end()); }

	const T& front() const { return *begin(); }
	const T& back() const { return *(--end()); }

	void swap(list<T>& ls) { std::swap(_head, ls._head); }
	bool empty() const { return _head->_next == _head; }
    
	iterator insert(iterator pos, const T& x = T())
	{
		node* cur = pos._ptr;
		node* new_node = new node(x);
		new_node->_prev = cur;
		new_node->_next = cur->_next;
		cur->_next->_prev = new_node;
		cur->_next = new_node;
		return new_node;
	}
	iterator erase(iterator pos)
	{
		node* cur = pos._ptr;
		node* prev = cur->_prev;
		node* next = cur->_next;
		prev->_next = next;
		next->_prev = prev;
		delete cur;
		return next;
	}

	void print()
	{
		for (node* i = _head->_next; i != _head; i = i->_next)
			cout << i->_val << ' ';
		cout << endl;
	}
};

}

#if 0
#include<iostream>
using namespace std;
#include<iterator>

namespace Wang
{
template<class T>
struct list_node
{
    T _val;
    list_node* _next;
    list_node* _prev;
    list_node(const T& x = T())
        :_val(x)
        ,_next(nullptr)
        ,_prev(nullptr)
    {}
};

#if 0
template<class T>
class list_iterator
{
    typedef list_node<T> node;
    typedef list_iterator<T> Self;
    node* _p;
public:

    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;

    list_iterator(node* p)
        :_p(p)
    {}
    
    Self& operator++()
    {
        _p = _p->_next;
        return *this;
    }
    
    Self& operator--()
    {
        _p = _p->_prev;
        return *this;
    }

    Self operator++(int)
    {
        Self tmp(*this);
        _p = _p->_next;
        return tmp;
    }
    Self operator--(int)
    {
        Self tmp(*this);
        _p = _p->_prev;
        return tmp;
    }

    bool operator==(const list_iterator<T>& t) const
    { return _p == t._p; }

    bool operator!=(const list_iterator<T>& t) const
    { return _p != t._p; }

    T& operator*()
    { return _p->_val; }

    T* operator->()
    { return &_p->_val; }
};

template<class T>
class list_const_iterator
{
    typedef list_node<T> node;
    typedef list_const_iterator<T> Self;
    node* _p;
public:

    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;

    list_const_iterator(node* p)
        :_p(p)
    {}
    
    Self& operator++()
    {
        _p = _p->_next;
        return *this;
    }
    
    Self& operator--()
    {
        _p = _p->_prev;
        return *this;
    }

    Self operator++(int)
    {
        Self tmp(*this);
        _p = _p->_next;
        return tmp;
    }
    Self operator--(int)
    {
        Self tmp(*this);
        _p = _p->_prev;
        return tmp;
    }

    bool operator==(const Self& t) const
    { return _p == t._p; }

    bool operator!=(const Self& t) const
    { return _p != t._p; }

    const T& operator*()
    { return _p->_val; }

    const T* operator->()
    { return &_p->_val; }
};

#endif

template<class T, class Ref, class Ptr>
class list_iterator
{
public:
    typedef list_node<T> node;
    typedef list_iterator<T, Ref, Ptr> Self;
    node* _p;

    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = Ptr;
    using reference = Ref;

    list_iterator(node* p)
        :_p(p)
    {}
    
    Self& operator++()
    {
        _p = _p->_next;
        return *this;
    }
    
    Self& operator--()
    {
        _p = _p->_prev;
        return *this;
    }

    Self operator++(int)
    {
        Self tmp(*this);
        _p = _p->_next;
        return tmp;
    }
    Self operator--(int)
    {
        Self tmp(*this);
        _p = _p->_prev;
        return tmp;
    }

    bool operator==(const Self& t) const
    { return _p == t._p; }

    bool operator!=(const Self& t) const
    { return _p != t._p; }

    Ref operator*()
    { return _p->_val; }

    Ptr operator->()
    { return &_p->_val; }
};

// 模板不会被编译
template<class T>
class list
{
    typedef list_node<T> node;
    node* _head;
public:
    typedef list_iterator<T, T&, T*> iterator;
    typedef list_iterator<T, const T&, const T*> const_iterator;

    iterator begin() { return _head->_next; }
    iterator end() { return _head; }

    const_iterator begin() const { return _head->_next; }
    const_iterator end() const { return _head; }

    list()
    {
        _head = new node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    ~list()
    {
        node* i = _head->_next;
        while(i != _head)
        {
            node* ne = i->_next;
            delete i;
            i = ne;
        }
        delete _head;
        _head = nullptr;
    }

    list(const list<T>& ls)
    {
        _head = new node;
        _head->_next = _head;
        _head->_prev = _head;
        node* i = ls._head->_next;
        while(i != ls._head)
        {
            push_back(i->_val);
            i = i->_next;
        }
    }

    void push_back(const T& x)
    {
        node* tail = _head->_prev;
        node* t = new node(x);
        t->_prev = tail;
        t->_next = _head;
        tail->_next = t;
        _head->_prev = t;
    }

    void insert(iterator pos, const T& x)
    {
        node* t = new node(x);
        node* cur = pos._p;

        t->_prev = cur;
        t->_next = cur->_next;

        cur->_next->_prev = t;
        cur->_next = t;
    }

    iterator erase(iterator pos)
    {
        node* cur = pos._p;
        node* next = cur->_next;
        node* prev = cur->_prev;
        prev->_next = next;
        next->_prev = prev;
        delete cur;
        return next;
    }
    void print()
    {
        for(node* i = _head->_next; i != _head; i = i->_next)
            cout << i->_val << ' ';
        cout << endl;
    }
};

} // namespace Wang;
#endif